// solver_dfs.cpp: Source file for the SolverDFS class.
// Written by Victor Luna Freire - victorclf@live.com
// Copyright (c) Victor Luna Freire. All rights reserved.
// Wednesday, October 28, 2009 2:40:32 PM

#include "solver_dfs.h"

// Static members initialization.
const Vec2i SolverDFS::UNDEFINED_PARENT_VERTEX = Vec2i(-1, -1);


// Start solving.
void SolverDFS::start_process(const Vec2i& startpos, const Vec2i& exitpos) 
{
	// Prepare the maze for processing.
	// Exclude walls from the DFS beforehand
	for(std::vector<std::string>::iterator vec_itr = maze.begin(); vec_itr != maze.end(); ++vec_itr)
		for(std::string::iterator s_itr = vec_itr->begin(); s_itr != vec_itr->end(); ++s_itr) {
			if(*s_itr == NO_WALL) *s_itr = UNTOUCHED;
			else *s_itr = IGNORED;
		}
	
	// Set the start position.
	cursor = startpos;
	maze[startpos.y][startpos.x] = FRONTIER;

	// Mark the exit.
	maze[exitpos.y][exitpos.x] = EXIT;
	
	// NOTE: Assuming the parents were already reset in the constructor. (warning for possible future change)
}


// Perform next step in the solution. Returns false if the maze is solved. Starts solving if it was not started before.
bool SolverDFS::next_step() 
{
	// Is the exit here?
	if(maze[cursor.y][cursor.x] == EXIT) return false;

	// Solution not found yet, keep moving...
	std::vector<Vec2i> adj_pos = get_adjacent_pos(cursor);
	
	for(std::vector<Vec2i>::const_iterator itr = adj_pos.begin(); itr != adj_pos.end(); ++itr) {
		if(maze[itr->y][itr->x] == UNTOUCHED) {
			// Found unexplored position to go to
			move_cursor(*itr);
			return true;
		}
	}

	// All adjacent vertexes have been explored. Backtracking...
	// move_cursor() returns false if the parent is invalid. This happens when we try to backtrack from the root, when the DFS has finished.
	return move_cursor(get_parent(cursor)); 
}


// Moves the cursor to the adjacent position specified. Returns false if the position is invalid!
bool SolverDFS::move_cursor(const Vec2i& dst) 
{
	if(dst == UNDEFINED_PARENT_VERTEX) return false;
	// Set dst's parent.
	set_parent(dst, cursor);
	// Set vertex status.
	if(maze[dst.y][dst.x] == FRONTIER) maze[cursor.y][cursor.x] = ADDED;
	else maze[cursor.y][cursor.x] = FRONTIER;
	// Update cursor.
	cursor = dst;
	return true;
}


// Returns the solution found. The returned vector will be empty if no solution has been found yet.
// HACK: Adding objects to the beginning of a std::vector is slow. We need to use a std::vector for compatibility with Boost.Python.
std::vector<Vec2i> SolverDFS::get_solution() 
{
	std::vector<Vec2i> solution;
	if(!is_done()) return solution;
	
	Vec2i solution_cursor = cursor;
	while(solution_cursor != UNDEFINED_PARENT_VERTEX) {
		solution.insert(solution.begin(), solution_cursor);
		solution_cursor = get_parent(solution_cursor);
	}

	return solution;
}


// Is the maze solved?
bool SolverDFS::is_done() const
{
	return maze[cursor.y][cursor.x] == EXIT;
}


#ifdef _DEBUG
#include "builder_prim.h"
int main() 
{
    int w, h;
	std::cin >> w >> h;
	BuilderPrim maze(w, h);
	maze.all_steps();
    std::cout << maze << "\n\n";
	SolverDFS solver(maze.get_maze(), Vec2i(1, 1), Vec2i(maze.true_width() - 2, maze.true_height() - 2));
	std::cout << solver << "\n\n";
	return 0;
}
#endif